/*
    前序遍历: [根节点][左子树的前序遍历结果][右子树的前序遍历结果]
        线索：前序遍历的第一个元素就是根节点
            但是我们不知道左子树和右子树的长度
    中序遍历: [左子树的中序遍历结果][根节点][右子树的中序遍历结果]
        线索：如果知道根节点，我们就能知道左子树和右子树的长度

    1. 获取根节点，前序遍历的第一个元素
    2. 找到根节点在中序遍历中的位置，就可以确定左子树和右子树的长度
    3. 重新构造左子树和右子树的前序和中序遍历集合，递归构造
*/
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty()) {
            return nullptr;
        }

        TreeNode* root = new TreeNode(preorder[0]);

        for (int i = 0; i < inorder.size(); i++) {
            // 在中序遍历中找到根节点的位置
            if (inorder[i] != root->val) {
                continue;
            }

            vector<int> left_preorder(preorder.begin() + 1, preorder.begin() + i + 1);
            vector<int> right_preorder(preorder.begin() + i + 1, preorder.end());
            vector<int> left_inorder(inorder.begin(), inorder.begin() + i);
            vector<int> right_inorder(inorder.begin() + i + 1, inorder.end());

            root->left = buildTree(left_preorder, left_inorder);
            root->right = buildTree(right_preorder, right_inorder);

            break;
        }

        return root;
    }
};

int main() {
    return 0;
}